#include <vector>
#include <iostream>
#include <algorithm>
#include <limits>
#include "conio.h"

using namespace std;

int partition(vector<int> &arr, vector<int> &indexes, int p, int q)
{
	int pivot = arr[q],
		l = p-1, r = p;
	while (r <= q)
	{
		if (arr[r] <= pivot)
		{
			++l;
			swap(arr[r], arr[l]);
			swap(indexes[r], indexes[l]);
		}
		++r;
	}
	return l;
}

void quick_sort_rec(vector<int> &arr, vector<int> &indexes, int p, int q)
{
	if (p >= q)
		return;
	int pivot_idx = partition(arr, indexes, p, q);
	quick_sort_rec(arr, indexes, p, pivot_idx-1);
	quick_sort_rec(arr, indexes, pivot_idx+1, q);
}

void quick_sort(vector<int> &players_sorted, vector<int> &indexes)
{
	indexes.resize(players_sorted.size());
	for (int i_idx = 1; i_idx < indexes.size(); ++i_idx)
	{
		indexes[i_idx] = i_idx;
	}

	quick_sort_rec(players_sorted, indexes, 0, players_sorted.size()-1);
}

void find_best_command(const vector<int> &players)
{
	vector<int> players_sorted = players,
		indexes;
	quick_sort(players_sorted, indexes);

	int l = 0, r = 0;
	int cur_sum = players_sorted[l],
		max_sum = numeric_limits<int>::min(),
		l_max, r_max;

	while(r != players_sorted.size()-1)
	{		
		char move = 'r'; 
		if (r > l+1 && players_sorted[r+1] > players_sorted[l] + players_sorted[l+1])
		{
				move = 'l';
		}

		if (move == 'r')
		{			
			++r;
			cur_sum += players_sorted[r];
		}
		else
		{
			cur_sum -= players_sorted[l];
			++l;					
		}

		if (r > l+1 && players_sorted[r+1] <= players_sorted[l] + players_sorted[l+1] && cur_sum > max_sum)
		{
			l_max = l;
			r_max = r;
			max_sum = cur_sum;
		}
	}

	cout << "Strength of the most efficient team : " << endl;
	cout << max_sum << endl;
	cout << "Players' numbers to take : " << endl;
	for (int i = l_max; i <= r_max; ++i)
		cout << indexes[i] << " ";
	cout << endl;
}

void main()
{
	vector<int> players;
	int n_players;
	cout << "Input number of candidate players:" << endl;
	cin >> n_players;
	cout << "Input players:" << endl;
	players.resize(n_players);
	for (int i = 0; i < n_players; ++i)
		cin >> players[i];

	find_best_command(players);
	_getch();
}